package com.tyrone.algorithm.uf;

/**
 * 并查集
 */
public class UF {
    private int[] eleAndGroup;      //记录结点元素和该元素所在分组的标识
    private int count;              //记录并查集中数据的分组个数

    public UF(int N){
        count=N;
        eleAndGroup= new int[N];
        for (int i = 0; i < N; i++) {
            eleAndGroup[i]=i;
        }
    }
    /**
     * 获取当前并查集中的数据有多少个分组
     * @return
     */
    public int count(){
        return count;
    }

    /**
     * 判断并查集中元素p和元素q是否在同一分组中
     * @param p
     * @param q
     * @return
     */
    public boolean connected(int p,int q) {
        return eleAndGroup[p]==eleAndGroup[q];
    }

    /**
     * 元素p所在分组的标识符
     * @param p
     * @return
     */
    public int find(int p){
        return eleAndGroup[p];
    }

    /**
     * 把p元素所在分组和q元素所在分组合并
     * @param p
     * @param q
     */
    public void union(int p,int q){
        if (connected(p, q)){
            return;
        }
        int pGroup = find(p);
        int qGroup = find(q);
        for (int i = 0; i < eleAndGroup.length; i++) {
            if (eleAndGroup[i]==pGroup){
                eleAndGroup[i]=qGroup;
            }
        }
        count--;
    }
}
